#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using vec = vector < int >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int T = 152510;
const int N = 35;

const int mod = 998244353;

int upd(const int& x) { return x + (x >> 31 & mod); }

struct modint {
	// only prime available
	// by Werner_Yin
	int val;
	modint() : val(0) {}
	template < typename T > modint(T x) : val(upd(x % mod)) {}
	friend modint operator + (const modint &a, const modint &b) { return upd(a.val + b.val - mod); }
	friend modint operator - (const modint &a, const modint &b) { return upd(a.val - b.val); }
	friend modint operator * (const modint &a, const modint &b) { return 1ll * a.val * b.val % mod; }
	template < typename T > friend modint operator ^ (modint x, T t) {
		modint res = 1; t %= mod - 1; for(; t; t >>= 1, x = x * x) if(t & 1) res = res * x; return res;
	}
	friend modint operator / (const modint &a, const modint &b) { return a * (b ^ (mod - 2)); }	
	template < typename T > friend modint operator + (const modint &a, const T &b) { return a + modint(b); }
	template < typename T > friend modint operator - (const modint &a, const T &b) { return a - modint(b); }
	template < typename T > friend modint operator * (const modint &a, const T &b) { return a * modint(b); }
	template < typename T > friend modint operator / (const modint &a, const T &b) { return a / modint(b); }
	template < typename T > friend void operator += (modint &a, const T &b) { a = a + b; }
	template < typename T > friend void operator -= (modint &a, const T &b) { a = a - b; }
	template < typename T > friend void operator *= (modint &a, const T &b) { a = a * b; }
	template < typename T > friend void operator ^= (modint &a, const T &b) { a = a ^ b; }
	template < typename T > friend void operator /= (modint &a, const T &b) { a = a / b; }
	friend bool operator == (const modint &a, const modint &b) { return a.val == b.val; }
	friend bool operator !(const modint &a) { return !a.val; }
	friend modint operator - (modint &a) { return upd(-a.val); }
	operator int() { return val; }
	operator bool() { return val > 0; }
};
using tmod = modint;
using pii = pair < tmod, tmod >;

pii mat[N][N];
int phi[T], pri[T], pnum, n, m, x[T], y[T], w[T];
bool v[T];

pii operator + (const pii &a, const pii &b) { return pii(a.fi + b.fi, a.se + b.se); }
pii operator - (const pii &a, const pii &b) { return pii(a.fi - b.fi, a.se - b.se); }
pii operator * (const pii &a, const pii &b) { return pii(a.fi * b.fi, a.se * b.fi + a.fi * b.se); }
pii operator / (const pii &a, const pii &b) { return pii(a.fi / b.fi, (a.se * b.fi - a.fi * b.se) / b.fi / b.fi); }

void init(int l) {
	phi[1] = 1; 
	rep(i, 2, l) {
		if(!v[i]) pri[++pnum] = i, phi[i] = i - 1;
		rep(j, 1, pnum) {
			if(pri[j] * i > l) break;
			v[pri[j] * i] = true;
			if(i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
			phi[i * pri[j]] = phi[i] * phi[pri[j]];
		}
	}
}

tmod Gauss() {
	pii res = { 1, 0 };
	rep(i, 1, n - 1) {
		int k = n; rep(j, i, n - 1) if(mat[j][i].fi) { k = j; break; }
		if(k == 0) return 0;
		if(k ^ i) res = pii{ 0, 0 } - res, swap(mat[i], mat[k]);
		rep(j, i + 1, n - 1) if(mat[j][i].fi || mat[j][i].se){
			pii t = mat[j][i] / mat[i][i];
			rep(k, i, n - 1) mat[j][k] = mat[j][k] - mat[i][k] * t;
		}
	}
	rep(i, 1, n - 1) res = res * mat[i][i];
	return res.se;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; int mx = 0;
	rep(i, 1, m) x[i] = in, y[i] = in, w[i] = in, chkmax(mx, w[i]);
	init(mx); tmod ans = 0;
	rep(d, 1, mx) {
		rep(i, 1, n) rep(j, 1, n) mat[i][j] = { 0, 0 };
		int cnt = 0; rep(i, 1, m) cnt += w[i] % d == 0; if(cnt < n - 1) continue;
		rep(i, 1, m)
			if(w[i] % d == 0) {
				int a = x[i], b = y[i], c = w[i];
				mat[a][a] = mat[a][a] + pii{ 1, c }; mat[b][b] = mat[b][b] + pii{ 1, c };
				mat[a][b] = mat[a][b] - pii{ 1, c }; mat[b][a] = mat[b][a] - pii{ 1, c };
			}
		ans = ans + Gauss() * phi[d];
	} printf("%d\n", (int)ans);
	return 0;
}
